//
//  ViewController.swift
//  ArithmeticClass7
//
//  Created by xiangzuhua on 2020/9/24.
//  Copyright © 2020 xiang. All rights reserved.
//

import UIKit

class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        // 单链表反转
//        self.testListReversal()
        
        // 链表中环的检测
//        self.testListCycle()
        
        // 两个有序链表合并为一个有序链表
//        self.testMergeTowList()
        
        // 删除链表中倒数第n个节点
//        self.testRemoveNthFromeEnd()
        
        // 求链表的中间节点
//        self.testFindCenterNode()
        
        // 顺序栈
//        self.testArrStack()
        
        // 动态顺序栈
//        self.testArrMutStack()
        
        // 链式栈
//        self.testLinkStack()
        
        // 冒泡排序
//        var items: [Int] = [7,3,5,6,2,9]
//        Sort_11.bubbleSort(&items)
//        print("冒泡排序")
//        // for循环数组中的元素
//        for index in items {
//            print(index)
//        }
        
        // 插入排序
//        var items1: [Int] = [9,4,8,2,4,7,2,1,8]
//        Sort_11.insertionSort(&items1)
//        print("插入排序")
//        for item in items1 {
//            print(item)
//        }
        
        // 选择排序
//        var items2: [Int] = [6,4,7,3,8,1,9]
//        Sort_11.selectSort1(&items2)
//        print("选择排序")
//        for item in items2 {
//            print(item)
//        }
        
        // 归并排序
//        var items = [3,2,6,9,6,4,8,1]
//        Sort_12.merge_sort(&items);
//        for item in items {
//            print(item)
//        }
        
        // 快速排序
//        var items = [9,5,9,7,3,5,7,1]
//        Sort_12.quick_sort(&items)
//        for item in items {
//            print(item)
//        }
        
        // 快速排序查找第K大的元素
//        var items = [9,10,3,6,8,3,4,7,11];
//        let k = Sort_12.LookForKthLargestElement(&items,k: 3)
//        print("第K大的元素:\(k)");
        
        // 桶排序 - 计数排序
//        var items: [Int] = [10,20,44,33,22,90,110,32,89,119,29,66,76,87,74,49,87,88,99,79,78]
//        Sort_13.countSort(&items, maxValue: 119)
//        for item in items {
//            print(item)
//        }
        
        // 桶排序 - 基数排序
//        var items: [String] = ["some","no","yes","girl","boy","something","where","what","apple","gone","a","anywhere","sure","baby"]
//        Sort_13.cardinalNumberSort(&items)
//        items.sort()
//        for item in items {
//            print(item)
//        }
        // 效率对比
//        efficiencyCompare()
        
        // 非递归二分查找
        
        
        //
        

        // Do any additional setup after loading the view.
    }
    
    func efficiencyCompare(){// 冒泡排序、插入排序、选择排序、归并排序、快速排序效率对比
        var bigItems: [Int] = [Int](repeating: 0, count: 10000)
        for (index,_) in bigItems.enumerated() {
            bigItems[index] = Int(arc4random()%10000)
        }

        var bigItems1 = bigItems
        var bigItems2 = bigItems
        var bigItems3 = bigItems
        var bigItems4 = bigItems
        var bigItems5 = bigItems

        let startTime1 = CFAbsoluteTimeGetCurrent()
        Sort_11.bubbleSort(&bigItems1)
        let endTime1 = CFAbsoluteTimeGetCurrent()
        print("冒泡排序耗时：\(endTime1 - startTime1)")

        let startTime2 = CFAbsoluteTimeGetCurrent()
        Sort_11.insertionSort(&bigItems2)
        let endTime2 = CFAbsoluteTimeGetCurrent()
        print("插入排序耗时：\(endTime2 - startTime2)")

        let startTime3 = CFAbsoluteTimeGetCurrent()
        Sort_11.insertionSort(&bigItems3)
        let endTime3 = CFAbsoluteTimeGetCurrent()
        print("选择排序耗时：\(endTime3 - startTime3)")
        
        let startTime4 = CFAbsoluteTimeGetCurrent()
        Sort_12.merge_sort(&bigItems4)
        let endTime4 = CFAbsoluteTimeGetCurrent()
        print("归并排序耗时：\(endTime4 - startTime4)")
        
        let startTime5 = CFAbsoluteTimeGetCurrent()
        Sort_12.quick_sort(&bigItems5)
        let endTime5 = CFAbsoluteTimeGetCurrent()
        print("快速排序耗时：\(endTime5 - startTime5)")
    }
    
    // 单链表反转
    func testListReversal() {
        
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let sixthNode = ListNode.init(6)
        let seventhNode = ListNode.init(7)

        firstNode.next = secondNode
        secondNode.next = thirdNode
        thirdNode.next = fourthNode
        fourthNode.next = fivethNode
        fivethNode.next = sixthNode
        sixthNode.next = seventhNode

        // 反转
//        print("反转方法一")
//        let reversal_result1: ListNode? =  LinkList_7.reversalList(firstNode)
//        var temp_reversal1: ListNode? = reversal_result1
//        while temp_reversal1 != nil {
//            print("node val:\(temp_reversal1!.val)")
//            temp_reversal1 = temp_reversal1?.next
//        }
        
        print("反转方法二")
        let reversal_result2: ListNode? = LinkList_7.recursionReversalList(firstNode)
        var temp_reversal2: ListNode? = reversal_result2
        while temp_reversal2 != nil {
            print("node val:\(temp_reversal2!.val)")
            temp_reversal2 = temp_reversal2?.next
        }
    }
    
    // 链表中环的检测
    func testListCycle() {
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let sixthNode = ListNode.init(6)
        let seventhNode = ListNode.init(7)
        let eighth = ListNode.init(8)

        firstNode.next = secondNode
        secondNode.next = thirdNode
        thirdNode.next = fourthNode
        fourthNode.next = fivethNode
        fivethNode.next = sixthNode
        sixthNode.next = seventhNode
        seventhNode.next = eighth
        eighth.next = thirdNode
        
        let cycle_result = LinkList_7.hasCycleList(firstNode)
        print("has cycle:\(cycle_result)")
    }
    
    // 两个有序链表合并为一个有序链表
    func testMergeTowList() {
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let sixthNode = ListNode.init(6)
        let seventhNode = ListNode.init(7)
        let eighth = ListNode.init(8)
        
        firstNode.next = thirdNode
        thirdNode.next = fivethNode
        fivethNode.next = seventhNode
        
        secondNode.next = fourthNode
        fourthNode.next = sixthNode
        sixthNode.next = eighth
        
        // 合并前
        var temp1: ListNode? = firstNode
        print("第一个有序链表")
        while temp1 != nil{
            print("node val:\(temp1!.val)")
            temp1 = temp1?.next
        }
        print("第二个有序链表")
        var temp2: ListNode? = secondNode
        while temp2 != nil {
            print("node val:\(temp2!.val)")
            temp2 = temp2?.next
        }
        
        // 合并后
//        print("使用方法一合并后的链表")
//        let merge_result1: ListNode? = LinkList_7.mergeTowList(firstNode, secondNode)
//        var tempResult1: ListNode? = merge_result1
//        while tempResult1 != nil {
//            print("node val:\(tempResult1!.val)")
//            tempResult1 = tempResult1?.next
//        }
        
        print("使用方法二合并后的链表")
        let merge_result2: ListNode? = LinkList_7.recurionMergeTwoList(l1: firstNode, l2: secondNode)
        var tempResult2: ListNode? = merge_result2
        while tempResult2 != nil {
            print("node val:\(tempResult2!.val)")
            tempResult2 = tempResult2?.next
        }
    }
    
    // 删除链表中倒数第n个节点
    func testRemoveNthFromeEnd() {
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let sixthNode = ListNode.init(6)
        let seventhNode = ListNode.init(7)
        let eighth = ListNode.init(8)

        firstNode.next = secondNode
        secondNode.next = thirdNode
        thirdNode.next = fourthNode
        fourthNode.next = fivethNode
        fivethNode.next = sixthNode
        sixthNode.next = seventhNode
        seventhNode.next = eighth
        
        print("删除倒数第n个节点")
        let remove_result = LinkList_7.removeNthFromeEnd(firstNode, n: 4)
        var temp_remove = remove_result
        while temp_remove != nil {
            print("node val:\(temp_remove!.val)")
            temp_remove = temp_remove?.next
        }
    }
    
    // 求链表的中间节点
    func testFindCenterNode(){
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let sixthNode = ListNode.init(6)
        let seventhNode = ListNode.init(7)
        let eighth = ListNode.init(8)

        firstNode.next = secondNode
        secondNode.next = thirdNode
        thirdNode.next = fourthNode
        fourthNode.next = fivethNode
        fivethNode.next = sixthNode
        sixthNode.next = seventhNode
        seventhNode.next = eighth
        
        print("寻找链表的中间节点")
        let find_result = LinkList_7.findCenterNode(firstNode)
        print("node val:\(String(describing: find_result?.val))")
    }
    
    // 顺序栈
    func testArrStack(){
        let arraySt: ArrayStack = ArrayStack.init(3)
        print(arraySt.push(item: "1"))
        print(arraySt.push(item: "2"))
        print(arraySt.push(item: "3"))
        print(arraySt.push(item: "4"))
        print(arraySt.pop())
        print(arraySt.pop())
        print(arraySt.pop())
        let id = arraySt.pop()
        print(id)
        
    }
    
    // 动态顺序栈
    func testArrMutStack(){
        let arraySt: ArrayMutabelStack = ArrayMutabelStack.init(3)
        print(arraySt.push(item: "222"))
        print(arraySt.push(item: "33"))
        print(arraySt.push(item: "dfsfa"))
        print(arraySt.push(item: "asfsdfs"))
        print(arraySt.pop())
        
    }
    
    // 链式栈
    func testLinkStack(){
        let firstNode = ListNode.init(1)
        let secondNode = ListNode.init(2)
        let thirdNode = ListNode.init(3)
        let fourthNode = ListNode.init(4)
        let fivethNode = ListNode.init(5)
        let linkStack: LinkStack = LinkStack.init(4)
        print(linkStack.push(firstNode))
        print(linkStack.push(secondNode))
        print(linkStack.push(thirdNode))
        print(linkStack.push(fourthNode))
        print(linkStack.push(fivethNode))
        print(linkStack.head!.val)
        print(linkStack.next!.val)
        
        print(linkStack.pop()?.val as Any)
        print(linkStack.pop()?.val as Any)
        print(linkStack.pop()?.val as Any)
        print(linkStack.pop()?.val as Any)
        print(linkStack.pop()?.val as Any)
        
        print(linkStack.head?.val as Any)
        print(linkStack.next?.val as Any)
    }
}

